//队列中的结点的结构体
typedef struct node
{
    int target;            //要去的站点号
    int servise_position;  //请求发生的站点号
    int servise_direction; // 0代表车内服务，1代表搭乘顺时针车的请求，2代表搭乘逆时针车的请求
    struct node *next;
} node;

typedef struct queue
{
    node *front; //队头指针
    node *end;   //队尾指针
    int size;
} queue;

//初始化队列=>构建一个只有头结点的空队
//参数：在主函数当中创建一个队列的结构体变量，将其作为参数传到init函数中
queue *init(queue *Q)
{
    node *head = (node *)malloc(sizeof(node)); // malloc一个头结点
    Q->front = Q->end = head;                  //队头指针，队尾指针都指向头结点
    Q->size = 0;                               //长度设置为0
    return Q;                                  //返回只有头结点的队列
}
//销毁队列
void destory(queue *Q)
{
    //一直循环，直到对队头指针指向空
    while (Q->front)
    {
        node *temp = Q->front;
        free(Q->front);
        Q->front = temp;
    }
}

//入队: 组成新的结点加在队尾,根据服务类型传递第一个参数，如果是站外服务就把target传成负一 ，如果车内服务的话 ，就把service position传成负一 
void push(int servise_direction, int servise_position, int target,queue *Q )
{
    node *newNode = (node *)malloc(sizeof(node));
    //存放得到的数据
    newNode->servise_direction = servise_direction;
    newNode->servise_position = servise_position;
    newNode->target = target; 
    // next域置空
    newNode->next = NULL;
    //插入新节点
    Q->end->next = newNode;

    Q->end = newNode;
    //队列长度加1
    Q->size++;
}

//
//出队
void pop(queue *Q)
{
    //队空的情况
    if (Q->front == Q->end)
        return;
    //暂存需要出队的结点
    node *temp = Q->front->next;
    //删除队列中的结点
    free(Q->front->next);
    Q->front->next = temp->next;

    //如果删除的恰好是尾结点
    if (Q->end == temp)
    {
        Q->end = Q->front;
    }
    //长度减1
    Q->size--;
    //返回队头元素
    return temp;
}

//链表判空,如果为空返回1，不为空返回0
int isEmpty(queue *Q)
{
    if (Q->front == Q->end)
        return 1;
    else
        return 0;
}

//获得队头元素
//因为队列是在main函数里面创建的，所以获取队头元素不需要调用函数，直接Q.front.next就是队头的节点